SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Prim's algorithm</title>

</head>

Prim's algorithm

</h1>

</header>

In <a href="Computer_science" title="Computer science">computer science</a>, Prim's algorithm is a <a href="Greedy_algorithm" title="Greedy algorithm">greedy algorithm</a> that finds a <a href="Minimum_spanning_tree" title="Minimum spanning tree">minimum spanning tree</a> for a <a href="Weighted_graph" class="mw-redirect" title="Weighted graph">weighted</a> <a href="Undirected_graph" class="mw-redirect" title="Undirected graph">undirected graph</a>. This means it finds a subset of the <a href="Edge_(graph_theory)" class="mw-redirect" title="Edge (graph theory)">edges</a> that forms a <a href="Tree_(graph_theory)" title="Tree (graph theory)">tree</a> that includes every <a href="Vertex_(graph_theory)" title="Vertex (graph theory)">vertex</a>, where the total weight of all the <a href="Graph_theory" title="Graph theory">edges</a> in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.

The algorithm was developed in 1930 by <a href="Czech_people" class="mw-redirect" title="Czech people">Czech</a> mathematician <a href="Vojt%C4%9Bch_Jarn%C3%ADk" title="Vojtěch Jarník">Vojtěch Jarník</a><a href="#cite_note-1">[1]</a> and later rediscovered and republished by <a href="Computer_scientist" title="Computer scientist">computer scientists</a> <a href="Robert_C._Prim" title="Robert C. Prim">Robert C. Prim</a> in 1957<a href="#cite_note-2">[2]</a> and <a href="Edsger_W._Dijkstra" title="Edsger W. Dijkstra">Edsger W. Dijkstra</a> in 1959.<a href="#cite_note-3">[3]</a> Therefore, it is also sometimes called the Jarník's algorithm,<a href="#cite_note-4">[4]</a> Prim–Jarník algorithm,<a href="#cite_note-5">[5]</a> Prim–Dijkstra algorithm<a href="#cite_note-chertar-6">[6]</a>

or the DJP algorithm.<a href="#cite_note-pr02-7">[7]</a>

Other well-known algorithms for this problem include <a href="Kruskal's_algorithm" title="Kruskal's algorithm">Kruskal's algorithm</a> and <a href="Bor%C5%AFvka's_algorithm" title="Borůvka's algorithm">Borůvka's algorithm</a>.<a href="#cite_note-8">[8]</a> These algorithms find the minimum spanning forest in a possibly disconnected graph; in contrast, the most basic form of Prim's algorithm only finds minimum spanning trees in connected graphs. However, running Prim's algorithm separately for each <a href="Connected_component_(graph_theory)" class="mw-redirect" title="Connected component (graph theory)">connected component</a> of the graph, it can also be used to find the minimum spanning forest.<a href="#cite_note-9">[9]</a> In terms of their asymptotic <a href="Time_complexity" title="Time complexity">time complexity</a>, these three algorithms are equally fast for <a href="Sparse_graph" class="mw-redirect" title="Sparse graph">sparse graphs</a>, but slower than other more sophisticated algorithms.<a href="#cite_note-pr02-7">[7]</a><a href="#cite_note-chertar-6">[6]</a>

However, for graphs that are sufficiently dense, Prim's algorithm can be made to run in <a href="Linear_time" class="mw-redirect" title="Linear time">linear time</a>, meeting or improving the time bounds for other algorithms.<a href="#cite_note-tarjan83p77-10">[10]</a>

<div class="mw-heading mw-heading2"><h2 id="Description">Description</h2></div>

The algorithm may informally be described as performing the following steps:

<div><ol><li>Initialize a tree with a single vertex, chosen arbitrarily from the graph.</li><li>Grow the tree by one edge: Of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree.</li><li>Repeat step 2 (until all vertices are in the tree).</li></ol></div>

In more detail, it may be implemented following the <a href="Pseudocode" title="Pseudocode">pseudocode</a> below.

<pre>function Prim(vertices, edges) is

for each vertex in vertices do

cheapestCost[vertex] ← ∞

cheapestEdge[vertex] ← null

explored ← empty set

unexplored ← set containing all vertices

startVertex ← any element of vertices

cheapestCost[startVertex] ← 0

while unexplored is not empty do

// Select vertex in unexplored with minimum cost

currentVertex ← vertex in unexplored with minimum cheapestCost[vertex]

unexplored.remove(currentVertex)

explored.add(currentVertex)

for each edge (currentVertex, neighbor) in edges do

if neighbor in unexplored and weight(currentVertex, neighbor) < cheapestCost[neighbor] THEN

cheapestCost[neighbor] ← weight(currentVertex, neighbor)

cheapestEdge[neighbor] ← (currentVertex, neighbor)

resultEdges ← empty list

for each vertex in vertices do

if cheapestEdge[vertex] ≠ null THEN

resultEdges.append(cheapestEdge[vertex])

return resultEdges

</pre>

As described above, the starting vertex for the algorithm will be chosen arbitrarily, because the first iteration of the main loop of the algorithm will have a set of vertices in Q that all have equal weights, and the algorithm will automatically start a new tree in F when it completes a spanning tree of each connected component of the input graph. The algorithm may be modified to start with any particular vertex s by setting C[s] to be a number smaller than the other values of C (for instance, zero), and it may be modified to only find a single spanning tree rather than an entire spanning forest (matching more closely the informal description) by stopping whenever it encounters another vertex flagged as having no associated edge.

Different variations of the algorithm differ from each other in how the set Q is implemented: as a simple <a href="Linked_list" title="Linked list">linked list</a> or <a href="Array_data_structure" class="mw-redirect" title="Array data structure">array</a> of vertices, or as a more complicated <a href="Priority_queue" title="Priority queue">priority queue</a> data structure. This choice leads to differences in the <a href="Time_complexity" title="Time complexity">time complexity</a> of the algorithm. In general, a priority queue will be quicker at finding the vertex v with minimum cost, but will entail more expensive updates when the value of C[w] changes.

<div class="mw-heading mw-heading2"><h2 id="Time_complexity">Time complexity</h2></div>

The time complexity of Prim's algorithm depends on the data structures used for the graph and for ordering the edges by weight, which can be done using a <a href="Priority_queue" title="Priority queue">priority queue</a>. The following table shows the typical choices:

<th>Minimum edge weight data structure</th>

<th>Time complexity (total)

</th></tr>

<tr>

<td><a href="Adjacency_matrix" title="Adjacency matrix">adjacency matrix</a>, searching</td>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|V|^{2})}</annotation>

</semantics>

</math><img src="./e1e99764e23be92b694aef042c6460ff921357e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.718ex; height:3.343ex;" alt="{\displaystyle O(|V|^{2})}" loading="lazy">

</td></tr>

<tr>

<td><a href="Binary_heap" title="Binary heap">binary heap</a> and <a href="Adjacency_list" title="Adjacency list">adjacency list</a></td>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O((|V|+|E|)\log |V|)=O(|E|\log |V|)}</annotation>

</semantics>

</math><img src="./19e7605c32e80569d7fb15473143e6e8487a2f80.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:37.787ex; height:2.843ex;" alt="{\displaystyle O((|V|+|E|)\log |V|)=O(|E|\log |V|)}" loading="lazy">

</td></tr>

<tr>

<td><a href="Fibonacci_heap" title="Fibonacci heap">Fibonacci heap</a> and <a href="Adjacency_list" title="Adjacency list">adjacency list</a></td>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|E|+|V|\log |V|)}</annotation>

</semantics>

</math><img src="./4fcb7644781d08e9e958d4a430a3107da04bf1b3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.4ex; height:2.843ex;" alt="{\displaystyle O(|E|+|V|\log |V|)}" loading="lazy">

</td></tr></tbody></table>

A simple implementation of Prim's, using an <a href="Adjacency_matrix" title="Adjacency matrix">adjacency matrix</a> or an <a href="Adjacency_list" title="Adjacency list">adjacency list</a> graph representation and linearly searching an array of weights to find the minimum weight edge to add, requires <a href="Big-O_notation" class="mw-redirect" title="Big-O notation">O</a>(|V|2) running time. However, this running time can be greatly improved by using <a href="Heap_(data_structure)" title="Heap (data structure)">heaps</a> to implement finding minimum weight edges in the algorithm's inner loop.

A first improved version uses a heap to store all edges of the input graph, ordered by their weight. This leads to an O(|E| log |E|) worst-case running time. But storing vertices instead of edges can improve it still further. The heap should order the vertices by the smallest edge-weight that connects them to any vertex in the partially constructed <a href="Minimum_spanning_tree" title="Minimum spanning tree">minimum spanning tree</a> (MST) (or infinity if no such edge exists). Every time a vertex v is chosen and added to the MST, a decrease-key operation is performed on all vertices w outside the partial MST such that v is connected to w, setting the key to the minimum of its previous value and the edge cost of (v,w).

Using a simple <a href="Binary_heap" title="Binary heap">binary heap</a> data structure, Prim's algorithm can now be shown to run in time <a href="Big-O_notation" class="mw-redirect" title="Big-O notation">O</a>(|E| log |V|) where |E| is the number of edges and |V| is the number of vertices. Using a more sophisticated <a href="Fibonacci_heap" title="Fibonacci heap">Fibonacci heap</a>, this can be brought down to <a href="Big-O_notation" class="mw-redirect" title="Big-O notation">O</a>(|E| + |V| log |V|), which is <a href="Asymptotic_computational_complexity" title="Asymptotic computational complexity">asymptotically faster</a> when the graph is <a href="Dense_graph" title="Dense graph">dense</a> enough that |E| is <a href="Big-O_notation" class="mw-redirect" title="Big-O notation">ω</a>(|V|), and <a href="Linear_time" class="mw-redirect" title="Linear time">linear time</a> when |E| is at least |V| log |V|. For graphs of even greater density (having at least |V|c edges for some c > 1), Prim's algorithm can be made to run in linear time even more simply, by using a <a href="D-ary_heap" title="D-ary heap">d-ary heap</a> in place of a Fibonacci heap.<a href="#cite_note-tarjan83p77-10">[10]</a><a href="#cite_note-11">[11]</a>

<div class="mw-heading mw-heading2"><h2 id="Proof_of_correctness">Proof of correctness</h2></div>

Let P be a connected, weighted <a href="Graph_theory" title="Graph theory">graph</a>. At every iteration of Prim's algorithm, an edge must be found that connects a vertex in a subgraph to a vertex outside the subgraph. Since P is connected, there will always be a path to every vertex. The output Y of Prim's algorithm is a <a href="Tree_(graph_theory)" title="Tree (graph theory)">tree</a>, because the edge and vertex added to tree Y are connected.

Let Y1 be a minimum spanning tree of graph P. If Y1=Y then Y is a minimum spanning tree. Otherwise, let e be the first edge added during the construction of tree Y that is not in tree Y1, and V be the set of vertices connected by the edges added before edge e. Then one endpoint of edge e is in set V and the other is not. Since tree Y1 is a spanning tree of graph P, there is a path in tree Y1 joining the two endpoints. As one travels along the path, one must encounter an edge f joining a vertex in set V to one that is not in set V. Now, at the iteration when edge e was added to tree Y, edge f could also have been added and it would be added instead of edge e if its weight was less than e, and since edge f was not added, we conclude that

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w(f)\geq w(e).}</annotation>

</semantics>

</math><img src="./cedd55ba247aa96d262dc181d9233cbcdd2fdc56.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.054ex; height:2.843ex;" alt="{\displaystyle w(f)\geq w(e).}" loading="lazy"></dd></dl>

Let tree Y2 be the graph obtained by removing edge f from and adding edge e to tree Y1. It is easy to show that tree Y2 is connected, has the same number of edges as tree Y1, and the total weights of its edges is not larger than that of tree Y1, therefore it is also a minimum spanning tree of graph P and it contains edge e and all the edges added before it during the construction of set V. Repeat the steps above and we will eventually obtain a minimum spanning tree of graph P that is identical to tree Y. This shows Y is a minimum spanning tree. The minimum spanning tree allows for the first subset of the sub-region to be expanded into a larger subset X, which we assume to be the minimum.

<div class="mw-heading mw-heading2"><h2 id="Parallel_algorithm">Parallel algorithm</h2></div>

The main loop of Prim's algorithm is inherently sequential and thus not <a href="Parallel_algorithm" title="Parallel algorithm">parallelizable</a>. However, the <a href="#step3c">inner loop</a>, which determines the next edge of minimum weight that does not form a cycle, can be parallelized by dividing the vertices and edges between the available processors.<a href="#cite_note-grama2003-12">[12]</a> The following <a href="Pseudocode" title="Pseudocode">pseudocode</a> demonstrates this.

<div><ol><li>Assign each processor <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{i}}</annotation>

</semantics>

</math><img src="./3ba1396129f7be3c7f828a571b6649e6807d10d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.292ex; height:2.509ex;" alt="{\displaystyle P_{i}}" loading="lazy"> a set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{i}}</annotation>

</semantics>

</math><img src="./f300b83673e961a9d48f3862216b167f94e5668c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.155ex; height:2.509ex;" alt="{\displaystyle V_{i}}" loading="lazy"> of consecutive vertices of length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {|V|}{|P|}}}">

<mfrac>

<mrow>

</mrow>

</mrow>

<mrow>

</mrow>

</mrow>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {|V|}{|P|}}}</annotation>

</semantics>

</math><img src="./7049f2c4d5fc53261b3b1b414127e917fdbe36fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:3.015ex; height:4.843ex;" alt="{\displaystyle {\tfrac {|V|}{|P|}}}" loading="lazy">.</li><li>Create C, E, F, and Q as in the <a href="#sequential_algorithm">sequential algorithm</a> and divide C, E, as well as the graph between all processors such that each processor holds the incoming edges to its set of vertices. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{i}}</annotation>

</semantics>

</math><img src="./cc49dc02c0ec8c86b67e7d10518ac791eda0bf22.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.461ex; height:2.509ex;" alt="{\displaystyle C_{i}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E_{i}}</annotation>

</semantics>

</math><img src="./8ba9f6e3041b052cf13a0ede4ecf35fb4c9cd16c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.515ex; height:2.509ex;" alt="{\displaystyle E_{i}}" loading="lazy"> denote the parts of C, E stored on processor <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{i}}</annotation>

</semantics>

<div><ol type="a"><li>On every processor: find the vertex <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{i}}</annotation>

</semantics>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{i}}</annotation>

</semantics>

</math><img src="./cc49dc02c0ec8c86b67e7d10518ac791eda0bf22.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.461ex; height:2.509ex;" alt="{\displaystyle C_{i}}" loading="lazy">[<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{i}}</annotation>

</semantics>

</math><img src="./7dffe5726650f6daac54829972a94f38eb8ec127.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.927ex; height:2.009ex;" alt="{\displaystyle v_{i}}" loading="lazy">] (local solution).</li><li><a href="Reduction_Operator" class="mw-redirect" title="Reduction Operator">Min-reduce</a> the local solutions to find the vertex v having the minimum possible value of C[v] (global solution).</li><li><a href="Broadcasting_(computing)" class="mw-redirect" title="Broadcasting (computing)">Broadcast</a> the selected node to every processor.</li><li>Add v to F and, if E[v] is not the special flag value, also add E[v] to F.</li><li>On every processor: update <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{i}}</annotation>

</semantics>

</math><img src="./cc49dc02c0ec8c86b67e7d10518ac791eda0bf22.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.461ex; height:2.509ex;" alt="{\displaystyle C_{i}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E_{i}}</annotation>

</semantics>

This algorithm can generally be implemented on distributed machines<a href="#cite_note-grama2003-12">[12]</a> as well as on shared memory machines.<a href="#cite_note-13">[13]</a> The running time is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O({\tfrac {|V|^{2}}{|P|}})+O(|V|\log |P|)}">

<mfrac>

<mrow>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

<mrow>

</mrow>

</mrow>

</mfrac>

</mstyle>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O({\tfrac {|V|^{2}}{|P|}})+O(|V|\log |P|)}</annotation>

</semantics>

</math><img src="./18b01ce4136f7723979797e6b8ea4303e28de358.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:23.718ex; height:5.176ex;" alt="{\displaystyle O({\tfrac {|V|^{2}}{|P|}})+O(|V|\log |P|)}" loading="lazy">, assuming that the reduce and broadcast operations can be performed in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log |P|)}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log |P|)}</annotation>

</semantics>

</math><img src="./45a349d595f6b6189539caf1a888107c5d8022c1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.981ex; height:2.843ex;" alt="{\displaystyle O(\log |P|)}" loading="lazy">.<a href="#cite_note-grama2003-12">[12]</a> A variant of Prim's algorithm for shared memory machines, in which Prim's sequential algorithm is being run in parallel, starting from different vertices, has also been explored.<a href="#cite_note-14">[14]</a> It should, however, be noted that more sophisticated algorithms exist to solve the <a href="Distributed_minimum_spanning_tree" title="Distributed minimum spanning tree">distributed minimum spanning tree</a> problem in a more efficient manner.

<ul><li><a href="Dijkstra's_algorithm" title="Dijkstra's algorithm">Dijkstra's algorithm</a>, a very similar algorithm for the <a href="Shortest_path_problem" title="Shortest path problem">shortest path problem</a></li>

<li><a href="Greedoid" title="Greedoid">Greedoids</a> offer a general way to understand the correctness of Prim's algorithm</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFJarník1930" class="citation cs2 cs1-prop-foreign-lang-source"><a href="Vojt%C4%9Bch_Jarn%C3%ADk" title="Vojtěch Jarník">Jarník, V.</a> (1930), "O jistém problému minimálním" [About a certain minimal problem], Práce Moravské Přírodovědecké Společnosti (in Czech), 6 (4): 57–63, <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/10338.dmlcz%2F500726">10338.dmlcz/500726</a></cite>.

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFPrim1957" class="citation cs2"><a href="Robert_C._Prim" title="Robert C. Prim">Prim, R. C.</a> (November 1957), <a rel="nofollow" class="external text" href="https://archive.org/details/bstj36-6-1389">"Shortest connection networks And some generalizations"</a>, <a href="Bell_System_Technical_Journal" class="mw-redirect" title="Bell System Technical Journal">Bell System Technical Journal</a>, 36 (6): 1389–1401, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1957BSTJ...36.1389P">1957BSTJ...36.1389P</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Fj.1538-7305.1957.tb01515.x">10.1002/j.1538-7305.1957.tb01515.x</a></cite>.

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFDijkstra1959" class="citation cs2"><a href="Edsger_W._Dijkstra" title="Edsger W. Dijkstra">Dijkstra, E. W.</a> (December 1959), <a rel="nofollow" class="external text" href="https://www-m3.ma.tum.de/twiki/pub/MN0506/WebHome/dijkstra.pdf">"A note on two problems in connexion with graphs"</a> (PDF), Numerische Mathematik, 1 (1): 269–271, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.165.7577">10.1.1.165.7577</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01386390">10.1007/BF01386390</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:123284777">123284777</a></cite>.

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFSedgewickWayne2011" class="citation cs2"><a href="Robert_Sedgewick_(computer_scientist)" title="Robert Sedgewick (computer scientist)">Sedgewick, Robert</a>; Wayne, Kevin Daniel (2011), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=MTpsAQAAQBAJ&pg=PA628">Algorithms</a> (4th ed.), Addison-Wesley, p. 628, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-321-57351-3</bdi></cite>.

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFRosen2011" class="citation cs2">Rosen, Kenneth (2011), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=6EJOCAAAQBAJ&pg=PA798">Discrete Mathematics and Its Applications</a> (7th ed.), McGraw-Hill Science, p. 798</cite>.

</li>

<li id="cite_note-chertar-6">^ <a href="#cite_ref-chertar_6-0">a</a> <a href="#cite_ref-chertar_6-1">b</a> <cite id="CITEREFCheritonTarjan1976" class="citation cs2"><a href="David_Cheriton" title="David Cheriton">Cheriton, David</a>; <a href="Robert_Tarjan" title="Robert Tarjan">Tarjan, Robert Endre</a> (1976), "Finding minimum spanning trees", <a href="SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a>, 5 (4): 724–742, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0205051">10.1137/0205051</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0446458">0446458</a></cite>.

</li>

<li id="cite_note-pr02-7">^ <a href="#cite_ref-pr02_7-0">a</a> <a href="#cite_ref-pr02_7-1">b</a> <cite id="CITEREFPettieRamachandran2002" class="citation cs2">Pettie, Seth; <a href="Vijaya_Ramachandran" title="Vijaya Ramachandran">Ramachandran, Vijaya</a> (January 2002), <a rel="nofollow" class="external text" href="http://www.cs.utexas.edu/~vlr/papers/optmsf-jacm.pdf">"An optimal minimum spanning tree algorithm"</a> (PDF), Journal of the ACM, 49 (1): 16–34, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.110.7670">10.1.1.110.7670</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F505241.505243">10.1145/505241.505243</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2148431">2148431</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:5362916">5362916</a></cite>.

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFTarjan1983" class="citation cs2"><a href="Robert_Tarjan" title="Robert Tarjan">Tarjan, Robert Endre</a> (1983), "Chapter 6. Minimum spanning trees. 6.2. Three classical algorithms", Data Structures and Network Algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 44, <a href="Society_for_Industrial_and_Applied_Mathematics" title="Society for Industrial and Applied Mathematics">Society for Industrial and Applied Mathematics</a>, pp. 72–77</cite>.

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFKepnerGilbert2011" class="citation cs2">Kepner, Jeremy; Gilbert, John (2011), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=JBXDc83jRBwC&pg=PA55">Graph Algorithms in the Language of Linear Algebra</a>, Software, Environments, and Tools, vol. 22, <a href="Society_for_Industrial_and_Applied_Mathematics" title="Society for Industrial and Applied Mathematics">Society for Industrial and Applied Mathematics</a>, p. 55, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780898719901</bdi></cite>.

</li>

<li id="cite_note-tarjan83p77-10">^ <a href="#cite_ref-tarjan83p77_10-0">a</a> <a href="#cite_ref-tarjan83p77_10-1">b</a> <a href="#CITEREFTarjan1983">Tarjan (1983)</a>, p. 77.

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFJohnson1975" class="citation cs2"><a href="Donald_B._Johnson" title="Donald B. Johnson">Johnson, Donald B.</a> (December 1975), "Priority queues with update and finding minimum spanning trees", Information Processing Letters, 4 (3): 53–57, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0020-0190%2875%2990001-0">10.1016/0020-0190(75)90001-0</a></cite>.

</li>

<li id="cite_note-grama2003-12">^ <a href="#cite_ref-grama2003_12-0">a</a> <a href="#cite_ref-grama2003_12-1">b</a> <a href="#cite_ref-grama2003_12-2">c</a> <cite id="CITEREFGramaGuptaKarypisKumar2003" class="citation cs2">Grama, Ananth; Gupta, Anshul; Karypis, George; Kumar, Vipin (2003), Introduction to Parallel Computing, Addison-Wesley, pp. 444–446, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0201648652</bdi></cite>

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite id="CITEREFQuinnDeo1984" class="citation cs2">Quinn, Michael J.; Deo, Narsingh (1984), "Parallel graph algorithms", ACM Computing Surveys, 16 (3): 319–348, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2514.2515">10.1145/2514.2515</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:6833839">6833839</a></cite>

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <cite id="CITEREFSetia2009" class="citation cs2">Setia, Rohit (2009), <a rel="nofollow" class="external text" href="https://ncit-cluster.grid.pub.ro/trac/PP2009/export/157/proiecte/pgraph/Documentation/parallelspannintree.pdf">"A new parallel algorithm for minimum spanning tree problem"</a> (PDF), Proc. International Conference on High Performance Computing (HiPC)</cite>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://meyavuz.wordpress.com/2017/03/10/prims-algorithm-animation-for-randomly-distributed-points">Prim's Algorithm progress on randomly distributed points</a></li>

<li> Media related to <a href="https://commons.wikimedia.org/wiki/Category:Prim%27s_algorithm" class="extiw external" title="commons:Category:Prim's algorithm">Prim's algorithm</a> at Wikimedia Commons</li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Graph_and_tree_traversal_algorithms231" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Graph_and_tree_traversal_algorithms231" style="font-size:114%;margin:0 4em"><a href="Graph_traversal" title="Graph traversal">Graph</a> and <a href="Tree_traversal" title="Tree traversal">tree</a> traversal algorithms</div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Graph_traversal" title="Graph traversal">Search</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Alpha%E2%80%93beta_pruning" title="Alpha–beta pruning">α–β pruning</a></li>

<li><a href="Best-first_search" title="Best-first search">Best-first search</a></li>

<li><a href="Beam_search" title="Beam search">Beam search</a></li>

<li><a href="Bidirectional_search" title="Bidirectional search">Bidirectional search</a></li>

<li><a href="Breadth-first_search" title="Breadth-first search">Breadth-first search</a>

<ul><li><a href="Lexicographic_breadth-first_search" title="Lexicographic breadth-first search">Lexicographic</a></li>

<li><a href="Parallel_breadth-first_search" title="Parallel breadth-first search">Parallel</a></li></ul></li>

<li><a href="Depth-first_search" title="Depth-first search">Depth-first search</a>

<ul><li><a href="Iterative_deepening_depth-first_search" title="Iterative deepening depth-first search">Iterative deepening</a></li></ul></li>

<li><a href="Fringe_search" title="Fringe search">Fringe search</a></li>

<li><a href="Jump_point_search" title="Jump point search">Jump point search</a></li>

<li><a href="Monte_Carlo_tree_search" title="Monte Carlo tree search">Monte Carlo tree search</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Shortest_path_problem" title="Shortest path problem">Shortest path</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bellman%E2%80%93Ford_algorithm" title="Bellman–Ford algorithm">Bellman–Ford</a></li>

<li><a href="Dijkstra's_algorithm" title="Dijkstra's algorithm">Dijkstra's</a></li>

<li><a href="Floyd%E2%80%93Warshall_algorithm" title="Floyd–Warshall algorithm">Floyd–Warshall</a></li>

<li><a href="Johnson's_algorithm" title="Johnson's algorithm">Johnson's</a></li>

<li><a href="Shortest_path_faster_algorithm" class="mw-redirect" title="Shortest path faster algorithm">Shortest path faster</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Minimum_spanning_tree" title="Minimum spanning tree">Minimum spanning tree</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bor%C5%AFvka's_algorithm" title="Borůvka's algorithm">Borůvka's</a></li>

<li><a href="Kruskal's_algorithm" title="Kruskal's algorithm">Kruskal's</a></li>

<li><a href="Reverse-delete_algorithm" title="Reverse-delete algorithm">Reverse-delete</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div><a href="List_of_algorithms#Graph_search" title="List of algorithms">List of graph search algorithms</a></div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-15" href="https://en.wikipedia.org/wiki/?title=Prim's_algorithm&oldid=1290601959">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>